#include "MergeSort.h"
#include <stdlib.h>

//对arr[l...r]进行partition操作
//返回 p，使得arr[l, p-1]<arr[p]; arr[p+1, r]>arr[p]
template<typename T>
int __partition(T arr[], int l, int r){

    swap(arr[l], arr[rand()%(r-l+1)+l]);
    T v = arr[l];
    // arr[l+1...j]<v; arr[j+1...i)>v;i的位置是当前考察的元素
    int j = l;
    for(int i=l+1; i<=r; i++){
        if(arr[i]<v){
            swap(arr[++j], arr[i]);
        }
    }
    swap(arr[l], arr[j]);
    return j;
}

template<typename T>
int __bi_partition(T arr[], int l, int r){

    swap(arr[l], arr[rand()%(r-l+1)+l]);
    T v = arr[l];
    // arr[l+1...i]<=v; arr[j...r)>=v;i的位置是当前考察的元素
    int i = l+1, j=r;
    while(true){
        while(i<=r && arr[i]<v) i++;
        while(j>=l+1 && arr[j]>v) j--;
        if(i>j) break;
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
    swap(arr[l], arr[j]);
    return j;
}
//对arr[l...r]部分进行快速排序
template<typename T>
void __quickSort(T arr[], int l, int r){

    //if(l>=r)
        //return;
    if(r-l <= 15){
        insertionSort(arr, l, r);
        return;
    }
    int p = __bi_partition(arr, l, r);
    __quickSort(arr, l, p-1);
    __quickSort(arr, p+1, r);
}

//对arr[l...r]部分进行快速排序
//将arr[l...r] 分为<v; =v; >v 三部分
//递归地对 <v ; >v 部分进行三路排序
template<typename T>
void __quickSort_3ways(T arr[], int l, int r){

    //if(l>=r)
        //return;
    if(r-l <= 15){
        insertionSort(arr, l, r);
        return;
    }
    //partition
    swap(arr[l], arr[rand()%(r-l+1)+l]);
    T v = arr[l];

    int lt = l; //arr[l+1...lt]<v
    int gt = r+1; //arr[gt...r]>v
    int i = l+1; //arr[lt+1...i]==v
    while(i<gt){
        if(arr[i]<v){
            swap(arr[i], arr[lt+1]);
            lt++;
            i++;
        }
        else if(arr[i]>v){
            swap(arr[i], arr[gt-1]);
            gt--;
        }
        else{
            i++;
        }
    }
    swap(arr[l], arr[lt]);
    __quickSort_3ways(arr, l, lt-1);
    __quickSort_3ways(arr, gt, r);
}

template<typename T>
void quickSort(T arr[], int n){

    srand(time(NULL));
    __quickSort_3ways(arr, 0, n-1);
}
